Dijkstra method
Algorithm for finding the shortest path
The next step is to use priority queue to log order to find the vertices to be explored. heapq. O((E+V)log V)
code:python
def shortest_path(
start, goal, num_vertexes, edges,
INF=9223372036854775807, UNREACHABLE=-1):
distances = INF * num_vertexes prev = None * num_vertexes while queue:
d, frm = heappop(queue)
# already know shorter path
continue
if frm == goal:
p = goal
while p != start:
path.append(p)
path.reverse()
return d, path
if distancesto > new_cost: # found shorter path
heappush(queue, (distancesto, to)) return UNREACHABLE
old version
code:python
from collections import defaultdict
from heapq import *
# fast input
import sys
input = sys.stdin.buffer.readline
INF = sys.maxsize
num_vertexes, num_edges, start, goal = map(int, input().split())
edges = defaultdict(dict)
distances = INF * num_vertexes shortest_path = defaultdict(list)
for i in range(num_edges):
a, b, c = map(int, input().split())
# edgesba = c # if bidirectional while queue:
d, frm = heappop(queue)
# already know shorter path
continue
if frm == goal: # goal
break
# found shorter path
heappush(queue, (distancesto, to)) shortest_pathto = (frm, to) # unreachable
print(-1)
else:
path = []
cur = goal
while True:
frm, to = shortest_pathcur path.append((frm, to))
cur = frm
if frm == start:
break
path.reverse()
print(distancesgoal, len(path)) for frm, to in path:
print(frm, to)
Modifications to this code
Clarify where to discard the shortest path when it is not necessary to show the shortest path.
Outputs the number of edges that make up a path, but often you want to sum the edge costs
---
This page is auto-translated from /nishio/ダイクストラ法. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.